// 搜索旋转排序数组2

package Leetcode;

class solution_081 {
    public boolean search(int[] nums, int target) {
        int length = nums.length;
        // 剪枝
        if (length == 0)
            return false;
        if (length == 1)
            return nums[0] == target ? true : false;
        // 二分查找
        int left = 0, right = length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target)
                return true;
            // 左侧有序
            if (nums[mid] > nums[0]) {
                if (target >= nums[0] && target < nums[mid])
                    right = mid - 1;
                else
                    left = mid + 1;

            } else if (nums[mid] < nums[0]) {
                if (nums[mid] < target && target <= nums[length - 1])
                    left = mid + 1;
                else
                    right = mid - 1;
                // 当mid指向的数字与0位置相等，要么0~mid相等，要么mid~length-1相等
            } else {
                // 查找0~mid是否有不相等的部分
                int i = mid;
                for (; i >= left; i--) {
                    if (nums[i] != nums[mid]) {
                        right = mid - 1;
                        break;
                    }
                }
                if (i == left - 1)
                    left = mid + 1;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        solution_081 s = new solution_081();
        int[] nums = new int[] { 1, 0, 1, 1, 1 };
        int target = 0;
        s.search(nums, target);
    }
}

public class Solution081 {
    public boolean search(int[] nums, int target) {
        int length = nums.length;
        if (length == 0) {
            return false;
        }
        if (length == 1) {
            return nums[0] == target;
        }
        int left = 0, right = length - 1;
        while (left <= right) {
            int mid = (left + right)/2;
            if (target == nums[mid])
                return true;
            if (nums[mid] == nums[left] && nums[mid] == nums[right]) {
                left++;
                right--;
            }
            // 左边有序
            else if (nums[mid] >= nums[left]) {
                // 判断target输入哪个部分
                if (nums[left] <= target && target < nums[mid])
                    right = mid - 1;
                else
                    left = mid + 1;
            }
            // 右边有序
            else {
                if (nums[mid] < target && target <= nums[right])
                    left = mid + 1;
                else
                    right = mid - 1;
            }
        }

        return false;
    }
}
